package com.sheng.leetcode.year2022.swordfingeroffer.day22;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/09/20
 *<p>
 * 剑指 Offer 56 - I. 数组中数字出现的次数<p>
 *<p>
 * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。<p>
 * 请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。<p>
 *<p>
 * 示例 1：<p>
 * 输入：nums = [4,1,4,6]<p>
 * 输出：[1,6] 或 [6,1]<p>
 *<p>
 * 示例 2：<p>
 * 输入：nums = [1,2,10,4,1,4,3,3]<p>
 * 输出：[2,10] 或 [10,2]<p>
 *<p>
 * 限制：<p>
 *<p>
 * 2 <= nums.length <= 10000<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0056 {

    @Test
    public void test01() {
        int[] nums = {4,1,4,6};
//        int[] nums = {1,2,10,4,1,4,3,3};
        System.out.println(Arrays.toString(new Solution().singleNumbers(nums)));
    }
}
class Solution {
    public int[] singleNumbers(int[] nums) {
        // 交换律
        // 结合律（即(a^b)^c == a^(b^c)）
        // 对于任何数x，都有x^x=0，x^0=x
        // 在java中"^"表示异或，异或运算相同为0，相异为1
        int n = 0;
        // 将数组从头到尾异或一遍，最后得到的答案肯定是两个只出现一次的值的异或的结果
        // 其他数字都出现了两次，在异或中全部抵消了
        // 由于两个数字肯定不一样，那么异或的结果肯定不为0
        // 也就是说这个结果数组的二进制表示至少有一个位为1
        for (int num : nums) {
            n ^= num;
        }
        // 我们在结果数组中找到第一个为1的位的位置，记为第n位。
        // 现在我们以第n位是不是1为标准把元数组中的数字分成两个子数组，
        // 第一个子数组中每个数字的第n位都是1，而第二个子数组中每个数字的第n位都是0
        // 依次为0000 0001 -> 0000 0010 -> 0000 0100 -> 0000 1000 -> 0001 0000 -> 0010 0000 -> 0100 0000 -> 1000 0000
        // 当与这种类型的数值进行异或的答案为0时，代表n的其中一位一定是0
        int k = 1;
        while ((n & k) == 0) {
            // 相当于 x *= 2
            k <<= 1;
        }
        int[] ints = new int[2];
        for (int num : nums) {
            if ((num & k) == 0) {
                ints[0] ^= num;
            } else {
                ints[1] ^= num;
            }
        }
        return ints;
    }
}
